package leetcode.动态规划;

import java.util.Arrays;

public class Leetcode354 {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        if(n==0){
            return 0;
        }
        Arrays.sort(envelopes,(a, b)->{
            if(a[0]==b[0]){
                return a[1] - b[1];
            }else return a[0] - b[0];
        }); //排序，使得后面一个长或者宽与前面相比相等或者大
        int[] dp = new int[n];
        //最长递增子序列二维问题，时间复杂度On2
        Arrays.fill(dp,1);//每一个就是子序列
        int max = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < i;j++){
                if(envelopes[i][1]>envelopes[j][1]&&envelopes[i][0]>envelopes[j][0]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}
